Both the Enumerable.Max extension method and the SortedSet<T>.Max property can be used to find the maximum value in
a SortedSet<T>. However, SortedSet<T>.Max is much faster than Enumerable.Max. For small
collections, the performance difference may be minor, but for large collections, it can be noticeable. The same applies for the Min
property as well.
Max and Min in SortedSet<T> exploit the fact that the set is implemented via a Red-Black
tree. The algorithm to find the Max/Min is "go left/right whenever possible". The operation has the time complexity
of O(h) which becomes O(ln(n)) due to the fact that the tree is balanced. This is much better than the O(n)
time complexity of extension methods.
Max and Min in ImmutableSortedSet<T> exploits a tree augmentation technique, storing the
Min, Max and Count values on each node of the data structure. The time complexity in this case is
O(1) that is significantly better than O(n) of extension methods.
Applies to:
What is the potential impact?
We measured a significant improvement both in execution time and memory allocation. For more details see the Benchmarks section from
the More info tab.
